#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>


//version 1  直接使用两个哈希表 测出来19ms
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        //第一个哈希表是存储字符个数的，第二个是存储前驱字符是什么
        unordered_map<char, int> chnum = {{'c', 0}, {'r', 0}, {'o', 0}, {'a', 0}, {'k', 0}};
        unordered_map<char, char> prev_ch = {{'c', 'k'}, {'r', 'c'}, {'o', 'r'}, {'a', 'o'}, {'k', 'a'}};
        //这里直接把c的前缀当成k，然后对于它的前缀特殊判断处理就好了！


        int n = croakOfFrogs.size();
        for(int i = 0; i < n; ++i){
            char cur = croakOfFrogs[i], prev = prev_ch[cur];
            chnum[cur]++;
            if(cur == 'c'){
                if(chnum[prev] != 0) chnum[prev]--;
            }
            else{
                if(chnum[prev] == 0) return -1;
                else chnum[prev]--;
            }
        }

        //出来之后，可能前面croa四个字母还有剩下的，还得判断
        for(auto& it : chnum) 
            if (it.first != 'k' && it.second != 0) return -1;

        return chnum['k'];
    }
};



//version 2 上面的效率一般，而且最大问题是：代码的复用性差，因为只能针对于croak的参数！
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        //未来可以支持外界传参使用！
        string t = "croak";
        int n = t.size();
        vector<int> hash(n, 0); //模拟哈希，对应下标位置就是t中对应下标的元素 按顺序存储元素即可
        unordered_map<char, int> Index;
        for(int i = 0; i < n; ++i) Index[t[i]] = i;

        for(int i = 0; i < croakOfFrogs.size(); ++i){
            int cur_index = Index[croakOfFrogs[i]], prev_index = cur_index - 1;
            hash[cur_index]++;
            if(prev_index == -1){
                if(hash[n - 1] != 0) --hash[n - 1];
            } 
            else{
                if(hash[prev_index] == 0) return -1;
                else hash[prev_index]--;
            }
        }

        for(int i = 0; i < n - 1; ++i)
            if(hash[i]) return -1;
        return hash[n - 1];
    }
};